package com.wujunshen.algorithm.leetcode.dynamic.programming;

/**
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/8/11 14:57<br>
 */
public class 柱状图中最大的矩形 {
    public int largestRectangleArea(int[] heights) {
        // 当遇到两边小于当前高度的时候就可以进行计算 因为更低的高度轮到更低的那个元素的时候计算过了
        // 也就是只计算当前高度最大的面积是多少
        //记录当前下标的柱子 左边比它低的第一根柱子
        int[] leftDp = new int[heights.length];
        //记录当前下标的柱子 右边比它低的第一根柱子
        int[] rightDp = new int[heights.length];

        //初始化
        //下标为0的柱子 默认-1位置比他低  并且使用-1进行宽度计算 不会出现问题
        leftDp[0] = -1;
        for (int i = 1; i < heights.length; i++) {
            int index = i - 1;
            //小于零说明到了第一根柱子 最左边
            while(index >= 0 && heights[index] >= heights[i]){
                //直接跳到比当前柱子矮的柱子 减少循环
                index = leftDp[index];
            }
            //比当前柱子低的第一根柱子
            leftDp[i] = index;
        }

        //和上边同样效果
        rightDp[heights.length - 1] = heights.length;
        for (int i = heights.length - 2; i >= 0; i--) {
            int index = i + 1;
            while (index <= heights.length - 1 && heights[index] >= heights[i]){
                index = rightDp[index];
            }
            rightDp[i] = index;
        }

        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            /*宽度*/
            int nowArea = heights[i] * (rightDp[i] - leftDp[i] - 1);

            if(nowArea > maxArea) {
                maxArea = nowArea;
            }
        }

        return maxArea;
    }
}
